#include"dfa.h"
#include <queue>
#include <iostream>

using std::pair;
using std::make_pair;

DFA::DFA() : starting(0) {}
	
DFA::DFA(DFA const & d) : rules(d.rules), starting(d.starting), accepting(d.accepting) {}
	
DFA::~DFA() {}
	
set<unsigned> DFA::allStates() const {
	set<unsigned> res = accepting;
	res.insert(starting);
	map<lefton, unsigned>::const_iterator it = rules.begin();
	for( ; it != rules.end(); ++it ) {
		res.insert((it -> first) . first);
		res.insert(it -> second);
	}
	return res;
}

unsigned DFA::feedTerminal(unsigned state, char terminal) const {
	if (state != 0) {
		map<lefton, unsigned>::const_iterator it = rules . find(std::make_pair(state, terminal));
		return (it == rules . end()) ? 0 : it -> second;
	}
	else
		return 0;
}

set<unsigned> DFA::feedTerminal(set<unsigned> const & states, char terminal) const {
	set<unsigned> res;
	set<unsigned>::const_iterator it = states . begin();
	for( ; it != states . end(); ++it ) {
		unsigned to = feedTerminal(*it, terminal);
		if (to != 0)
			res.insert(to);
	}
	return res;
}

unsigned DFA::feedString(unsigned state, std::string const & str) const {
	string::const_iterator it = str . begin();
	for( ; (state != 0) && (it != str . end()); ++it )
		state = feedTerminal(state, *it);
	return state;
}

set<unsigned> DFA::feedString(set<unsigned> const & states, std::string const & str) const {
	set<unsigned> res = states;
	string::const_iterator it = str . begin();
	for( ; (!res . empty()) && (it != str . end()); ++it )
		res = feedTerminal(res, *it);
	return res;
}

unsigned DFA::startingState() const {
	return starting;
}

set<unsigned> const & DFA::acceptingStates() const {
	return accepting;
}

bool DFA::isAccepting(unsigned state) const {
	return (accepting . find(state) != accepting . end());
}

bool DFA::isAccepting(set<unsigned> const & states) const {
	set<unsigned> big = (states . size() > accepting . size()) ? states : accepting,
				small = (states . size() > accepting . size()) ? accepting : states;
	set<unsigned>::const_iterator it = small . begin();
	bool res = false;
	for( ; !res && (it != small . end()) ; ++it )
		res = (big . find(*it) != big . end());
	return res;
}

std::set< char > DFA::getAlphabet() const {

	std::set< char > alphabet;
	map< lefton, unsigned >::const_iterator it = rules.begin();

	for (; it != rules.end(); ++it) {
		alphabet.insert( it->first.second );
	}

	return alphabet;
}
set < set < unsigned >,  CompareSet > DFA::partition() const {

	set < set < unsigned >,  CompareSet > splitters;
	set< char > alphabet = getAlphabet();
	set < set < unsigned >,  CompareSet > partition;
	set< unsigned > states = allStates();	

	partition.insert (accepting);
	partition.insert (setDifference(states, accepting));
	
	splitters.insert (accepting);

	while (! splitters.empty() ) {	
	
		set< unsigned > sp = *(splitters.begin());
		splitters.erase(splitters.begin());

		for ( set< char >::const_iterator ait = alphabet.begin(); ait != alphabet.end(); ++ait) {

			set < unsigned > intoSplitter;
			for ( set< unsigned >::const_iterator it = states.begin(); it != states.end(); ++it) {
				if ( sp.find( feedTerminal(*it,*ait) ) != sp.end() ) 
					intoSplitter.insert ( *it );						
			}

			set < set < unsigned >,  CompareSet >::const_iterator pit = partition.begin();
			set < set < unsigned >,  CompareSet > tmp; 
			for ( ; pit != partition.end(); ++pit ) {
				
				set<unsigned> inters = setIntersection (*pit,intoSplitter);
				set<unsigned> dif = setDifference (*pit,intoSplitter);
		
				if (!inters.empty() && !dif.empty()) {
						tmp.insert(inters);	
						tmp.insert(dif);
						splitters.insert(inters);
				}
				else {
					tmp.insert(*pit);
				}
			}
			partition = tmp;	
			intoSplitter.clear();		
		}
	}

	return partition;
}

DFA DFA::mimimize() const {
	
	using std::endl;
	using std::cout;

	set < set < unsigned >,  CompareSet > p = partition();
	set < set < unsigned >,  CompareSet >::const_iterator pit = p.begin();
	map < set < unsigned >, unsigned, CompareSet > newNames;
	DFA minDFA;
	
	// add rules
	for ( ; pit != p.end(); ++pit) {

		unsigned newset;
		if ( newNames.find(*pit) == newNames.end() ) {
			newset = names . addOrRename( concatName(*pit) );			
			newNames . insert(make_pair(*pit, newset));
		}
		else 
			newset = newNames[*pit];
	
		set< char > alphabet = getAlphabet();
		set< char >::iterator ait = alphabet.begin();
		for ( ; ait != alphabet.end(); ++ait) {

			unsigned resN = feedTerminal(*(pit->begin()),*ait);
			set < unsigned > resSet; 
			unsigned toSet;

			// get the set corresponding to the resulting N-Terminal -
			set < set < unsigned >,  CompareSet >::const_iterator ppit = p.begin();
			/*for ( ; ppit != p.end(); ++ppit ) {
				if ( ppit->find(resN) != p.end() )
					resSet = *ppit;
			}*/
			for ( ; ppit != p.end(); ++ppit ) {
				if ( ppit->find(resN) != ppit->end() ) {
					resSet = *ppit;
					break;
				}
			}
			// check if the set is already renamed
			if ( newNames.find(resSet) == newNames.end() ) {
				toSet = names . addOrRename( concatName(resSet) );				
				newNames . insert(make_pair(*ppit, toSet));				
			}
			else { 

				toSet = newNames[resSet];
			}
			minDFA.rules.insert( make_pair (make_pair (newset, *ait), toSet) );
		}		


	}

	// add starting state
	set < set < unsigned >,  CompareSet >::const_iterator ppit = p.begin();
	set < unsigned > startingSet;
	for ( ; ppit != p.end(); ++ppit ) {
			if ( ppit->find(starting) != ppit->end() ) startingSet = *ppit;
	}
	minDFA.starting = newNames[startingSet];

	// add accepting states	

	set < unsigned >:: const_iterator ait = accepting.begin(); 
	
	for ( ; ait != accepting.end(); ++ait ) {
		
		set < unsigned > acceptingSet;
		for ( ppit = p . begin() ; ppit != p.end(); ++ppit ) {
				if ( ppit->find(*ait) != ppit->end() ) acceptingSet = *ppit;
		}

		minDFA.accepting.insert( newNames[acceptingSet] );
	}	
	return minDFA;
}
/*
bool DFA::isEmpty() const
*/
     
DFA & DFA::operator= (DFA const & d) {
	rules = d . rules;
	starting = d . starting;
	accepting = d . accepting;
	return *this;
}


/*DFA DFA::operator* () const {

	DFA dfaRes(*this);
	set<unsigned>::const_iterator it = dfaRes.accepting.begin();

	for ( ; it != dfaRes.accepting.end(); it++){
		dfaRes.rules.insert(make_pair(make_pair(*it, char(0)), dfaRes.starting));
	}
	return dfaRes;
}


DFA DFA::operator+ (DFA const & dfa1) const {

	DFA dfaRes;

	dfaRes.starting = starting;
	dfaRes.rules = rules;
	
	map<unsigned,unsigned> renamed;

	map<lefton, unsigned>::const_iterator it = dfa1.rules.begin();

	for ( ; it != dfa1.rules.end(); it++){
		map<unsigned,unsigned>::const_iterator itf1, itf2;
		itf1 = renamed.find(it->first.first);
		itf2 = renamed.find(second);

		if (itf1 == names.end()){
			first = names.addOrRename(names[it->first.first]);
			renamed.insert(make_pair(it->first.first,first));
		}
		else {	
			first = itf1->second;
		}
		if (itf2 == names.end()){
			second = names.addOrRename(names[it->second]);
			renamed.insert(make_pair(it->second,second));
		}
		else {
			second = itf2->second;
		}
		dfaRes.rules.insert(make_pair(first, it->first.second), second);
	}

	set<unsigned>::const_iterator its = dfa1.accepting.begin();
	for ( ; its != accepting.end(); its++){
		dfaRes.accepting.insert(renamed.find(*its));
	}
	return dfaRes;	
}

DFA DFA::operator| (DFA const & dfa1) const {

	DFA dfaRes;
	// создать новое стартовое состояние и кинуть его в новый автомат
	string newStartName = names[starting] + "_";
	dfaRes.starting = names.addName(newStartName);
	
	// кинуть все состояния из нашего автомата в новый автомат
	set<lefton, unsigned>::const_iterator it = rules.begin();
	for ( ; it != accepting.end(); it++){
		dfaRes.rules.insert(*it);
	}

	// кинуть все состояния из входящего автомата в наш автомат
	it = dfa1.rules.begin();
	for ( ; it != dfa1.accepting.end(); it++){
		dfaRes.rules.insert(make_pair(updateId(it->first.first), it->first.second), updateId(it->second));
	}

	// создать новое финальное состояние
	string newAcceptingName = names[*(accepting.begin())] + "_";
	dfaRes.newAcceptingName = names.addName(newAcceptingName);

	// из всех состояний нового автомата, которые были финальными в нашем автомате, добавить эпсилон-переходы в новое состояние
	set<unsigned>::const_iterator it = accepting.begin();

	for ( ; it != accepting.end(); it++){
		dfaRes.rules.insert(make_pair(make_pair(*it, char(0)), dfaRes.newAcceptingName));
	}

	// из всех состояний нового автомата, которые были финальными в автомате-параметре, добавить эпсилон-переходы в новое состояние

	it = dfa1.accepting.begin();
	for ( ; it != dfa1.accepting.end(); it++){
		dfaRes.rules.insert(make_pair(make_pair(updateId(*it), char(0)), dfaRes.newAcceptingName));
	}
	return dfaRes;
}*/

/*
DFA & DFA::operator|= (DFA const &);
DFA & DFA::operator&= (DFA const &);
DFA & DFA::operator+= (DFA const &);
bool DFA::operator== (DFA const &) const;
DFA DFA::operator! () const;
DFA DFA::operator| (DFA const &) const;
DFA DFA::operator& (DFA const &) const;



     
istream & operator>>(istream & in, DFA & d) {
	
}
*/

std::ostream & operator<<(std::ostream & stream, DFA const & dfa) {
	stream << "digraph DFA {" << std::endl;
	if (dfa . accepting . find(dfa . starting) == dfa . accepting . end())
		stream << "\"" << DFA::names[dfa . starting] << "\" [style = filled, color = green];" << std::endl;
	else
		stream << "\"" << DFA::names[dfa . starting] << "\" [style = filled, color = yellow];" << std::endl;
        for( set<unsigned>::const_iterator it = dfa . accepting . begin(); it != dfa . accepting . end(); ++it )
		if (*it != dfa . starting)
			stream << "\"" << DFA::names[*it] << "\" [style = filled, color = red];" << std::endl;
        for( map<lefton, unsigned>::const_iterator it = dfa . rules . begin(); it != dfa . rules . end(); ++it )
                stream << "\"" << DFA::names[it -> first . first] << "\" -> \"" << DFA::names[it -> second] << "\" [label = \"" << ((it -> first . second) ? (it -> first . second) : ' ') << "\"];" << std::endl;
        stream << "}" << std::endl;
        return stream;

}
